/**
 * @file 131.PalindromePartition.cc
 * @author snow-tyan (zziywang@163.com)
 * @brief {Life is too short to learn cpp.}
 * @version 0.1
 * @date 2021-11-14
 * 
 * @copyright Copyright (c) 2021
 * 
 * 切割问题
 * 131.分割回文串
 * 93.复原IP地址
 */

#include <algorithm>
#include <iostream>
#include <string>
#include <unordered_map>
#include <vector>
using namespace std;
// #define TEST131

template <typename T>
void print(const T &Containers)
{
    typename T::const_iterator it = Containers.begin();
    while (it != Containers.end()) {
        cout << *it << " ";
        ++it;
    }
    cout << endl;
}

class Solution
{
#ifdef TEST131
private:
    vector<vector<string>> res;
    vector<string> path;

public:
    vector<vector<string>> partition(string s)
    {
        backtracking131(s, 0);
        return res;
    }

private:
    bool isPalindrome(string &s)
    {
        int i = 0, j = s.length() - 1;
        while (i < j) {
            if (s[i++] != s[j--]) {
                return false;
            }
        }
        return true;
    }

    void backtracking131(string &s, int startidx)
    {
        if (startidx == s.length()) {
            res.emplace_back(path);
            return;
        }
        for (int i = startidx; i < s.length(); ++i) {
            string sub = s.substr(startidx, i - startidx + 1);
            if (!isPalindrome(sub)) {
                continue;
            }
            path.emplace_back(sub);
            backtracking131(s, i + 1);
            path.pop_back();
        }
    }
#endif
private:
    vector<string> res;
    string path;

public:
    // 93.
    vector<string> restoreIpAddresses(string s) {
        backtracking93(s, 0, 0);
        return res;
    }
private:
    bool isValid(string &s){
        if (s.empty() || s.length() > 3){ // 四位数必大于255
            return false;
        }
        // cout << s << endl;
        // 含前导0不合法，单0合法
        // 大于255不合法
        if (s.length() != 1 && s.front() == '0' || stoi(s) > 255){
            return false;
        }
        return true;
    }

    void backtracking93(string &s, int startIdx, int pointNum){
        if (pointNum == 3){
            // 检查第四段
            string lastStr = s.substr(startIdx);
            if (isValid(lastStr)){
                path.append(lastStr);
                res.emplace_back(path);
            }
            return;
        }
        for (int i = startIdx; i < s.length(); ++i){
            string sub = s.substr(startIdx, i - startIdx + 1);
            if (!isValid(sub)){
                continue;
            }
            auto lastBegin = path.end(); // 上次的尾迭代器
            sub.push_back('.');
            path.append(sub);
            ++pointNum;
            backtracking93(s, i + 1, pointNum);
            --pointNum;
            path.erase(lastBegin, path.end());
        }
    }
};

Solution solve = Solution();

#ifdef TEST131
void test131()
{
    string s = "aabb";
    auto nums = solve.partition(s);
    for (auto &num : nums) {
        print(num);
    }
}
#endif

void test93()
{
    // string s = "25525511135";
    string s = "010010";
    auto res = solve.restoreIpAddresses(s);
    print(res);
}

int main()
{
    // test131();
    test93();
    return 0;
}